package com.ds.bintree.LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 从前序与中序遍历序列构造二叉树(递归分治法)
 * @date 2022/9/14 18:12
 */
public class Num105_PreAndInBuildTree {

    Map<Integer,Integer> inorderindex = new HashMap<>(); //根据值找索引，创建中序遍历的一个索引值，减少时间复杂度

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0 ; i< inorder.length;i++){
            inorderindex.put(inorder[i],i);
        }
        return mybuildTree(0,preorder.length-1,0,inorder.length-1,preorder);
    }


    /**
     * 画个图把前序遍历数组和中序遍历数组的左右区间索引搞明白就很简单了，就是每次递归找到一个子树的根节点，至于怎么找交给递归函数
     * @param pleft
     * @param pright
     * @param inleft
     * @param inright
     * @param preorder
     * @return
     */
    public TreeNode mybuildTree(int pleft, int pright, int inleft,int inright,int[] preorder){
        if (pleft-pright>0 || inleft-inright>0){
            return null;
        }
        int pivot = inorderindex.get(preorder[pleft]);
        TreeNode root = new TreeNode(preorder[pleft]);
        root.left = mybuildTree(pleft+1,pivot-inleft+pleft,inleft,pivot-1,preorder);
        root.right = mybuildTree(pivot-inleft+pleft+1,pright,pivot+1,inright,preorder);
        return root;
    }
}
